/*
** Copyright (C) 2009 Joshua Brent Marsh <joshua@icub3d.com>
**  
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 3 of the License, or
** (at your option) any later version.
**  
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
** GNU General Public License for more details.
**  
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**  
*/

/* $Id: test_list.c 44 2009-11-15 15:23:14Z joshua@icub3d.com $ */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

#include <CUnit/Basic.h>

#include "../src/list.h"
#include "../src/function_prototypes.h"

#include "test_helpers.h"
#include "test_list.h"

List *list;
List *clist;

int
init_test_list_suite ()
{
  /* create the two types of lists. */
  if ((clist = list_create_circular ()) == NULL)
    return 1;

  if ((list = list_create ()) == NULL)
    {
      list_destroy (clist, &dest_int);
      return 1;
    }
  else
    return 0;
}

int
clean_test_list_suite ()
{
  /* Clean up the lists. */
  list_destroy (list, &dest_int);
  list_destroy (clist, &dest_int);

  return 0;
}

void
test_list_insert ()
{
  int *cur;

  /* Test insert with empty list. */
  cur = create_int (1);
  CU_ASSERT (list_size (list) == 0);
  CU_ASSERT (list_insert (list, 3, cur) == 0);
  CU_ASSERT (list_insert (list, -3, cur) == 0);
  CU_ASSERT (list_insert (list, 0, cur) == 1);

  /* Test insert at end. */
  cur = create_int (3);
  CU_ASSERT (list_insert (list, 1, cur) == 1);

  /* Test insert in middle. */
  cur = create_int (2);
  CU_ASSERT (list_insert (list, 1, cur) == 1);

  /* Test insert at end. */
  cur = create_int (4);
  CU_ASSERT (list_insert (list, -3, cur) == 0);
  CU_ASSERT (list_insert (list, 4, cur) == 0);
  CU_ASSERT (list_insert (list, 3, cur) == 1);
  CU_ASSERT (list_size (list) == 4);

  /* Test helper functions. */
  cur = create_int (0);
  CU_ASSERT (list_insert_first (list, cur) == 1);

  cur = create_int (5);
  CU_ASSERT (list_insert_last (list, cur) == 1);
  CU_ASSERT (list_size (list) == 6);

  /* Test circular insert  with empty list. */
  cur = create_int (1);
  CU_ASSERT (list_insert_first (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 1);

  /* Test more inserts at head, tail, and middle. */
  cur = create_int (3);
  CU_ASSERT (list_insert_last (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 2);

  cur = create_int (0);
  CU_ASSERT (list_insert_first (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 3);

  cur = create_int (4);
  CU_ASSERT (list_insert_last (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 4);

  cur = create_int (2);
  CU_ASSERT (list_insert (clist, 2, cur) == 1);
  CU_ASSERT (list_size (clist) == 5);
}

void 
test_list_get ()
{
  /* Test gets at head, tail, and middle. */
  CU_ASSERT (list_size (list) == 6);
  CU_ASSERT (*(int *)list_get_first (list) == 0);
  CU_ASSERT (*(int *)list_get_last (list) == 5);

  CU_ASSERT (list_size (list) == 6);
  CU_ASSERT (*(int *)list_get (list, 0) == 0);
  CU_ASSERT (*(int *)list_get (list, 1) == 1);
  CU_ASSERT (*(int *)list_get (list, 2) == 2);
  CU_ASSERT (*(int *)list_get (list, 3) == 3);
  CU_ASSERT (*(int *)list_get (list, 4) == 4);
  CU_ASSERT (*(int *)list_get (list, 5) == 5);
  CU_ASSERT (list_size (list) == 6);

  CU_ASSERT (list_size (clist) == 5);
  CU_ASSERT (*(int *)list_get (clist, 0) == 0);
  CU_ASSERT (*(int *)list_get (clist, 1) == 1);
  CU_ASSERT (*(int *)list_get (clist, 2) == 2);
  CU_ASSERT (*(int *)list_get (clist, 3) == 3);
  CU_ASSERT (*(int *)list_get (clist, 4) == 4);
  CU_ASSERT (list_size (clist) == 5);

  /* Test invalid gets. */
  CU_ASSERT (list_get (list, -1) == NULL);
  CU_ASSERT (list_get (list, 1000) == NULL);
  CU_ASSERT (list_get (list, 6) == NULL);
}

void
test_list_remove ()
{
  int *cur;
  
  /* Test removal at head, tail, and middle. */
  CU_ASSERT (list_size (list) == 6);
  CU_ASSERT (* (int *)(cur = list_remove_first (list)) == 0);
  free (cur);
  CU_ASSERT (list_size (list) == 5);

  CU_ASSERT (* (int *)(cur = list_remove_last (list)) == 5);
  free (cur);
  CU_ASSERT (list_size (list) == 4);

  CU_ASSERT (* (int *)(cur = list_remove (list, 1)) == 2);
  free (cur);
  CU_ASSERT (list_size (list) == 3);

  /* Test removal at head, tail, and middle for recursive. */
  CU_ASSERT (list_size (clist) == 5);
  CU_ASSERT (* (int *)(cur = list_remove_first (clist)) == 0);
  free (cur);
  CU_ASSERT (list_size (clist) == 4);

  CU_ASSERT (* (int *)(cur = list_remove_last (clist)) == 4);
  free (cur);
  CU_ASSERT (list_size (clist) == 3);

  CU_ASSERT (* (int *)(cur = list_remove (clist, 1)) == 2);
  free (cur);
  CU_ASSERT (list_size (clist) == 2);

  /* Test some invalid removals. */
  CU_ASSERT (list_remove (list, -1) == NULL);
  CU_ASSERT (list_remove (list, 1000) == NULL);
  CU_ASSERT (list_remove (list, 3) == NULL);

}

void
test_list_insert2()
{
  int *cur;

  /* Test insert at head, tail, and middle for both list types after
     removal. */
  CU_ASSERT (list_size (list) == 3);
  cur = create_int (0);
  CU_ASSERT (list_insert_first (list, cur) == 1);

  CU_ASSERT (list_size (list) == 4);
  cur = create_int (5);
  CU_ASSERT (list_insert_last (list, cur) == 1);

  CU_ASSERT (list_size (list) == 5);
  cur = create_int (2);
  CU_ASSERT (list_insert (list, 2, cur) == 1);

  CU_ASSERT (list_size (list) == 6);

  cur = create_int (2);
  CU_ASSERT (list_insert (clist, 1, cur) == 1);
  CU_ASSERT (list_size (clist) == 3);

  cur = create_int (0);
  CU_ASSERT (list_insert_first (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 4);

  cur = create_int (4);
  CU_ASSERT (list_insert_last (clist, cur) == 1);
  CU_ASSERT (list_size (clist) == 5);

}

void
test_list_traverser ()
{
  int *data;
  ListTraverser trav;

  /* Test traversal. */
  list_traverser_init (&trav, list);
  CU_ASSERT (list_traverser_cur (&trav) == NULL);
  CU_ASSERT (list_traverser_remove (&trav) == NULL);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 4);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 4);
  CU_ASSERT (list_traverser_next (&trav) == NULL);
  CU_ASSERT (list_traverser_next (&trav) == NULL);
  CU_ASSERT (*(int *)list_traverser_prev (&trav) == 3);
  CU_ASSERT ((data = list_traverser_remove (&trav)) != NULL);
  free (data);

  list_traverser_init (&trav, list);
  CU_ASSERT (*(int *)list_traverser_prev (&trav) == 4);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 4);
  CU_ASSERT (*(int *)list_traverser_prev (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (list_traverser_prev (&trav) == NULL);
  CU_ASSERT (list_traverser_prev (&trav) == NULL);

  /* Test traversal circular. We should get repeats and no NULLs */
  list_traverser_init (&trav, clist);
  CU_ASSERT (list_traverser_cur (&trav) == NULL);
  CU_ASSERT (list_traverser_remove (&trav) == NULL);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 3);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 3);

  CU_ASSERT ((data = list_traverser_remove (&trav)) != NULL);
  free (data);

  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);

  /* Test inserts and then traversal again. */
  data = create_int (0);
  CU_ASSERT (list_traverser_insert_before (&trav, data) == 1);

  data = create_int (2);
  CU_ASSERT (list_traverser_insert_after (&trav, data) == 1);
  CU_ASSERT (list_size (clist) == 3);

  CU_ASSERT (*(int *)list_traverser_next (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);

  CU_ASSERT (*(int *)list_traverser_next (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);

  CU_ASSERT (*(int *)list_traverser_next (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);

  CU_ASSERT (*(int *)list_traverser_next (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 2);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav) == 1);

}

void
test_list_copy ()
{
  List *copy;
  ListTraverser trav1, trav2;
  size_t x;
  int *o, *c;

  copy = list_copy (list, copy_int, dest_int);
  CU_ASSERT (copy != NULL);
  CU_ASSERT (list_size (list) == list_size (copy));

  /* Vefify the copies are the same, but their memory isn't. */
  for (x = 0; x < list_size (list); x++)
    {
      o = list_get (list, x);
      c = list_get (copy, x);

      CU_ASSERT (*o == *c);
      CU_ASSERT (o != c);
    }
  
  list_destroy (copy, dest_int);
  
  /* Similar test, but without copying the data. */
  copy = list_copy (clist, NULL, NULL);
  CU_ASSERT (copy != NULL);
  CU_ASSERT (list_size (clist) == list_size (copy));
  list_traverser_init (&trav1, clist);  
  list_traverser_init (&trav2, copy);  

  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 2);

  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 2);
  
  /* Verify the memory locations are the same. */
  for (x = 0; x < 100; x++)
    {
      CU_ASSERT ((int *) list_traverser_next (&trav1) ==
		 (int *) list_traverser_next (&trav2));
      CU_ASSERT ((int *) list_traverser_cur (&trav1) ==
		 (int *) list_traverser_cur (&trav2));
    }

  list_destroy (copy, NULL);

}

void
test_list_serialize ()
{
  char *cur = NULL;
 
  /* Verify that the strings equal what we expect. */
  cur = list_serialize (list, serialize_int);
  CU_ASSERT (strcmp (cur, "2 0 1 11 4") == 0);
  free (cur);

  cur = list_serialize (clist, serialize_int);
  CU_ASSERT (strcmp (cur, "3 1 1 01 11 2") == 0);
  free (cur);
  
}

void
test_list_deserialize ()
{
  List *l, *m;
  ListTraverser trav1, trav2;
  size_t x;
  int *o, *c;
  
  /* Test and empty list. */
  l = list_deserialize ("0 0 ", deserialize_int, dest_int);
  CU_ASSERT (l != NULL);
  CU_ASSERT (list_size (l) == 0);
  list_destroy (l, dest_int);

  /* A few failure cases. */
  l = list_deserialize ("0 9 ", deserialize_int, dest_int);
  CU_ASSERT (l == NULL);

  l = list_deserialize ("2 0 0 1 4", deserialize_int, dest_int);
  CU_ASSERT (l == NULL);

  /* Test a regular list. */
  l = list_deserialize ("2 0 1 11 4", deserialize_int, dest_int);
  CU_ASSERT (l != NULL);
  CU_ASSERT (list_size (l) == 2);

  for (x = 0; x < list_size (l); x++)
    {
      o = list_get (list, x);
      c = list_get (l, x);

      CU_ASSERT (*o == *c);
      CU_ASSERT (o != c);
    }
  
  list_destroy (l, dest_int);

  /* test a circular list. */
  m = list_deserialize ("3 1 1 01 11 2", deserialize_int, dest_int);
  CU_ASSERT (m != NULL);
  CU_ASSERT (list_size (m) == 3);
  list_traverser_init (&trav1, clist);  
  list_traverser_init (&trav2, m);  

  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav1) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav1) == 2);

  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 0);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 0);
  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 1);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 1);
  CU_ASSERT (*(int *)list_traverser_next (&trav2) == 2);
  CU_ASSERT (*(int *)list_traverser_cur (&trav2) == 2);
  
  list_destroy (m, dest_int);
}

int
make_list_suite (CU_pSuite s)
{
  s = CU_add_suite ("Test List Suite", 
		    init_test_list_suite, 
		    clean_test_list_suite);
  if (s == NULL)
    {
      return CU_get_error();
    }

  if (CU_add_test (s, "test list_insert's", test_list_insert) == NULL ||
      CU_add_test (s, "test list_get's", test_list_get) == NULL ||
      CU_add_test (s, "test list_remove's", test_list_remove) == NULL ||
      CU_add_test (s, "test list_insert's 2", test_list_insert2) == NULL ||
      CU_add_test (s, "test list_remove's 2", test_list_remove) == NULL ||
      CU_add_test (s, "test list_traverser's", test_list_traverser) == NULL ||
      CU_add_test (s, "test list_copy's", test_list_copy) == NULL ||
      CU_add_test (s, "test list_serialize's", test_list_serialize) == NULL ||
      CU_add_test (s, "test list_deserialize's", test_list_deserialize) == NULL
      )
    {
      return CU_get_error();
    }

  return CU_get_error();
}
